1. Field of the Invention
The present invention relates generally to communication networks and more particularly to the design of communication paths of tree structure within a communication network between an ingress node and an egress node the network.
2. Description of the Related Art
In a label-switched communication system, such as ATM (asynchronous transfer mode) and MPLS (multiprotocol label switching) systems, an active communication path is provisioned between an ingress node and an egress node for carrying normal traffic and, in most cases, one or more spare paths are provisioned for purposes of protection switching or distributing overflow traffic. However, a large number of virtual channel identifiers (VCIs) and virtual path identifiers (VPIs) must be registered if all possible routes are provisioned between all pairs of ingress and egress nodes. In order to overcome this problem, a technique known “VP/VC merge” has been proposed, whereby multiple communication paths are provisioned using a single VPI or VCI.
In a communication system where a single VPI/VCI is used for identifying multiple paths provisioned between an ingress and an egress node, the structure of the paths is treated as a tree and the egress node assumes the root of the tree so that traffic is carried in the opposite sense. It is thus desirable that the number of such trees be as small as possible to reduce the number of labels (i.e., VPIs and VCIs) to a minimum.
One approach to designing a tree is to use the Dijkstra method (“Saitekika Handbook, Iri et al, Asakura Shoten publishing company), whereby all possible routes from one egress node to each ingress node are searched for in an attempt to determine shortest paths from which a tree is formed. A tree is formed by a technique known as the minimum spanning tree method (“Enshuu Graph Riron”, Iri et al, Korona-sha publishing company), in which the tree is defined as one in which the total sum of branch metrics is at a minimum. Such a tree can be obtained by a technique known as the Kruskal method.
While the known techniques allow provisioning of a single tree between an ingress node and an egress node, it is impossible to design a plurality of trees between these nodes.